#include "./../../../include/online/RecommendWords/EditDistance.h"

// 求取一个字符占据的字节数
size_t nBytesCode(const char ch)
{
    if (ch & (1 << 7))
    {
        int nBytes = 1;
        for (int idx = 0; idx != 6; ++idx)
        {
            if (ch & (1 << (6 - idx)))
            {
                ++nBytes;
            }
            else
                break;
        }
        return nBytes;
    }
    return 1;
}

// 计算字符串的字符个数（适用于 UTF-8 编码，处理多字节字符）
size_t length(const string &str)
{
    size_t ilen = 0; // 字符计数
    for (size_t idx = 0; idx != str.size(); ++idx)
    {
        // 获取当前字符占用的字节数（支持多字节字符）
        int nBytes = nBytesCode(str[idx]);

        // 跳过当前字符的剩余字节（适用于 UTF-8 编码）
        idx += (nBytes - 1);

        // 计数+1，代表找到一个完整的字符
        ++ilen;
    }
    return ilen;
}


// 返回三者的最小值
int triple_min(const int &a, const int &b, const int &c)
{
    if(a < b)
    {
        if(a < c)
        {
            return a;
        }
        else
        {
            return c;
        }
    }
    else
    {
        if(b<c)
        {
            return b;
        }
        else
        {
            return c;
        }
    }
}

// 中英文通用的最小编辑距离算法
int editDistance(const string &lhs, const string &rhs)
{
    // 计算最小编辑距离，支持处理中英文
    size_t lhs_len = length(lhs);
    size_t rhs_len = length(rhs);

    // 前缀匹配优化
    if (rhs.find(lhs) == 0)
        return rhs_len - lhs_len; // lhs 是 rhs 的前缀
    if (lhs.find(rhs) == 0)
        return lhs_len - rhs_len; // rhs 是 lhs 的前缀

    int editDist[lhs_len + 1][rhs_len + 1];

    for (size_t idx = 0; idx <= lhs_len; ++idx)
    {
        editDist[idx][0] = idx;
    }
    for (size_t idx = 0; idx <= rhs_len; ++idx)
    {
        editDist[0][idx] = idx;
    }

    string sublhs, subrhs;
    for (size_t dist_i = 1, lhs_idx = 0; dist_i <= lhs_len; ++dist_i, ++lhs_idx)
    {
        size_t nBytes = nBytesCode(lhs[lhs_idx]);
        sublhs = lhs.substr(lhs_idx, nBytes);
        lhs_idx += (nBytes - 1);

        for (size_t dist_j = 1, rhs_idx = 0; dist_j <= rhs_len; ++dist_j, ++rhs_idx)
        {
            nBytes = nBytesCode(rhs[rhs_idx]);
            subrhs = rhs.substr(rhs_idx, nBytes);
            rhs_idx += (nBytes - 1);

            if (sublhs == subrhs)
            {
                editDist[dist_i][dist_j] = editDist[dist_i - 1][dist_j - 1];
            }
            else
            {
                editDist[dist_i][dist_j] = triple_min(
                    editDist[dist_i][dist_j - 1] + 1,        // 插入
                    editDist[dist_i - 1][dist_j] + 1,        // 删除
                    editDist[dist_i - 1][dist_j - 1] + 1     // 替换
                );
            }
        }
    }
    return editDist[lhs_len][rhs_len];
}
